#!/usr/bin/python
#***************************************************************************
# Copyright notice for this file:
#  Copyright (C) 2012 TheAxeMan
#  _______ _                               _    _
# |__   __| |     ___     /\          ___ | \  / |
#    | |  | |__  / _ \   /  \  __  _ / _ \|  \/  | __ _ _ __
#    | |  | '_ \|  __/  / /\ \ \ \/ |  __/| .  . |/ _` | '_ \
#    | |  | | | | (__/\/ ____ \ )  (| (__/| |\/| | (_| | | | |
#    |_|  |_| |_|\____/_/    \_._/\_.\____|_|  |_|\__,_|_| |_|
#
# Final Fantasy TAS scripts by TheAxeMan
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#***************************************************************************

if __name__ == "__main__":
  import sys
  if globals().has_key('init_modules'):
    for m in [x for x in sys.modules.keys() if x not in init_modules]:
      del(sys.modules[m])
  else:
    init_modules = sys.modules.keys()

import sys
import re
import string
import time

from gamedata import GameData
from gamestate import GameState
from rundata import RunSegment
from rundata import RunSegments
from metarundata import MetaRunSegment
from metarundata import MetaRunSegments
from resultdata import ResultSegment
from resultdata import ResultSegments
from costfunctions import CostFunction


"""
A class to record the information for a tree-based simulation.
This class functions as both the root and nodes for the recursion.

attributes:
  gdata - game data for use
  cost_func - cost function to evaluate at the end nodes
  gstate - game state at this node
  cost_to_node - incremental cost up to node
  last_fight - last fight from the previous section (-1 for no fight)
  metarun - MetaRunSegments structure containing remaining run

"""
class TreeSimNode:
  def makeNextNode(self):
    """Add links to the static items"""
    next_node = TreeSimNode()
    next_node.gdata = self.gdata
    next_node.cost_func = self.cost_func
    return next_node

  def getCostsForAllSeeds(self, metarun_in, cost_func_in, gdata_in, gstate_in, do_status_bar=True):
    """Gets costs for all seeds of a metarun. Uses recursion to reuse simulation data."""
    self.cost_func = cost_func_in
    self.gdata = gdata_in
    self.cost_to_node = 0
    self.metarun = metarun_in
    self.metarun.resetOptionSet()

    #Print out the pcount. Make sure to do this before splitting the metarun.
    pcount = metarun_in.permutationCount()
    print "permutation count is", pcount

    #create the root node
    root_node = self.makeNextNode()
    if do_status_bar:
      self.status_bar = StatusBar()
      #the +1 suppresses the extra .
      self.status_bar.start(40, pcount+1)
      root_node.status_bar = self.status_bar

    #self.metarun will have no regressable segments after this split
    #root node gets first regression on
    root_node.metarun = self.metarun.splitOnFirstRegression()
    #make the run for the first non-regressable part
    section_segs = self.metarun.makeRunSegments(0, False, False)
    #set the node up with a gamestate copy
    root_node.gstate = gstate_in.copy()
    #simulate this first non-regressable part
    fight_list = getFightListFromSegments(section_segs, root_node.gdata, root_node.gstate)
    #calculate and store incremental cost function result
    root_node.cost_to_node = root_node.cost_func.costFunctionByFightList(section_segs, fight_list)
    #store last fight if present
    if len(fight_list) > 0:
      root_node.last_fight = fight_list[-1]
    else:
      root_node.last_fight = -1

    #DEBUG
    #record number of fights so far
    #root_node.fight_count = len(fight_list)

    #ready to start recursing!
    cost_func_results = root_node.getCostsForAllSeedsRecurse(do_status_bar)
    #now put the metarun back together
    metarun_in.addSegments(root_node.metarun)
    if do_status_bar:
      self.status_bar.finish()
    #return results
    return cost_func_results

  def getCostsForAllSeedsRecurse(self, do_status_bar):
    """
    On calling this, the first segment should be regressable.
    This is mandatory to make implementation easier.
    First, split off the first part up to a regressable segment or
    the end, whichever comes first. Then simulate all permutations
    of that stretch. For each one, recurse to simulate all
    permutations following that one. Return a list of cost function
    results.
    """
    #if we get an empty list, end things quickly
    if len(self.metarun.run) == 0:
      if do_status_bar:
        self.status_bar.incrementStatus()
      #print "completed leaf, cost is",self.cost_to_node
      #self.metarun.printOptionStatus()
      #print ""
      return [self.cost_to_node]
      #DEBUG
      #return [self.cost_to_node, self.fight_count]


    #print "recursive call in progress"
    #print "cost to node is", self.cost_to_node
    #print "metarun length is", len(self.metarun.run)
    #print "fights so far:", self.fight_count
    #print "last fight was", self.last_fight
    #print "game state:",
    #self.gstate.printState()
    #print ""

    #init result array
    cost_func_results = []

    #first metaseg should be regressable
    #split everything else to a separate metarun for now
    remaining_metarun = self.metarun.splitOnFirstRegression(False)
    #This node's metarun should only have only one segment now:
    #the one to regress. Error otherwise.
    if len(self.metarun.run) != 1:
      print "Recursion error! On node entry, metarun split results are invalid:"
      print "metarun size is", len(self.metarun.run)
      self.metarun.printRun(self.gdata, True)
      sys.exit()

    #If the regression is an option, declare it set in the
    #remaining metarun now.  This needs to be done before
    #splitting off the next node. But don't set the option
    #in the regression part since this is important for
    #regression. In fact, if it's already set we have a problem!
    #While we're at it, remember the pcount for this segment/node.
    regress_seg = self.metarun.run[0]
    if regress_seg.try_option:
      if self.metarun.option_set[regress_seg.option_id]:
        print "Recursion error: On node entry, first seg is an already-set option"
        remaining_metarun.printOptionStatus()
        sys.exit()
      remaining_metarun.option_set[regress_seg.option_id] = True
      pcount = 2
    else:
      pcount = regress_seg.permutationCount()

    #print "pcount at this recursion is",pcount
    #print "*** regression metarun:"
    #self.metarun.printRun(self.gdata, True)
    #print "remaining metarun:"
    #remaining_metarun.printRun(self.gdata, True)
    #print "remaining option status:"
    #remaining_metarun.printOptionStatus()
    #self.metarun.printRun(self.gdata, True)
    #print ""

    #start thinking about the next node
    next_node = self.makeNextNode()
    if do_status_bar:
      next_node.status_bar = self.status_bar
    #split off next node's meta run from remaining
    next_node.metarun = remaining_metarun.splitOnFirstRegression()

    #print "next node metarun:"
    #print ""
    #next_node.metarun.printRun(self.gdata, True)
    #print "next node option status:"
    #next_node.metarun.printOptionStatus()
    #print ""

    #Remaining_metarun might have references to the option in
    #the regression. Otherwise, we could generate the runSegments
    #from that section just once and reuse them.

    #recombine the remaining into this node's metarun
    self.metarun.addSegments(remaining_metarun)
    #init cost func results
    cost_func_results = []


    #Ok, now it's time to simulate all permutations of this section.
    #For each permutation, we'll set up the next node and recurse to
    #cover the rest of the run.
    for seed in range(pcount):
      #generate run for this section and seed. Last two arguments
      #tell generator not to include notes or reset options set
      #print "making run section with seed", seed

      #need to make sure all options are claimed to be set
      #this helps make pcount accurate
      self.metarun.resetOptionSet(True)
      #however if the current regression is an option, don't set that
      if regress_seg.try_option:
        self.metarun.option_set[regress_seg.option_id] = False

      section_segs = self.metarun.makeRunSegments(seed, False, False)
      #section_segs.printRun()
      #copy current gamestate to next node in preparation for simulation
      next_node.gstate = self.gstate.copy()
      #simulate to get fight_list and update game state
      fight_list = getFightListFromSegments(section_segs, self.gdata, next_node.gstate, False)

      #calculate cost for next node
      #incremental cost function component
      next_node.cost_to_node = self.cost_to_node + self.cost_func.costFunctionIncremental(section_segs, fight_list, self.last_fight)
      #print "section cost is",next_node.cost_to_node

      #if regression was an option there are some extra chores
      if regress_seg.try_option:
        #if enabled, update next node cost with option cost
        if self.metarun.option_flags[regress_seg.option_id]:
          next_node.cost_to_node += self.metarun.option_costs[regress_seg.option_id]
        #don't forget to propagate option value to node!
        next_node.metarun.option_flags[regress_seg.option_id] = self.metarun.option_flags[regress_seg.option_id]

      #update last_fight for next node
      if len(fight_list) > 0:
        next_node.last_fight = fight_list[-1]
      else:
        next_node.last_fight = self.last_fight

      #DEBUG
      #record number of fights so far
      #next_node.fight_count = self.fight_count + len(fight_list)

      #print "right before recursion"
      #print "next node metarun:"
      #next_node.metarun.printRun(self.gdata, True)
      #print "next node option status:"
      #next_node.metarun.printOptionStatus()
      #print ""

      #We need to record the option set list so that after
      #the recursive call we can get back to where we started.
      temp_op_set = next_node.metarun.option_set[:]

      #now make the recursive call and build up results
      cost_func_results += next_node.getCostsForAllSeedsRecurse(do_status_bar)

      #restore option set
      next_node.metarun.option_set = temp_op_set

    #recombine metarun and return results
    self.metarun.addSegments(next_node.metarun)
    return cost_func_results

def countNoRunFights(fight_list, gdata):
  """returns number of no-run fights in a fight list"""
  total = 0
  for fight in fight_list:
    enemy_group_name = gdata.enemy_groups[fight]
    if enemy_group_name in gdata.noRunList:
      total += 1
  return total

class StatusBar:
  def start(self, status_size, pcount):
    """starts out the status bar and makes a blank to start the .s"""

    self.status_size = status_size
    self.status = 0
    self.pcount = pcount
    self.dot_count = 0
    self.start_time = time.time()

    quarter_status = self.status_size / 4
    status_bar = "|"
    for y in range(4):
      for x in range(quarter_status-1):
        status_bar += "-"
      if y < 3:
        status_bar += "+"
      else:
        status_bar += "|"
    print status_bar
    sys.stdout.write(" ")

  def finish(self):
    finish_time = time.time()
    print ""
    print "finished in",finish_time-self.start_time,"seconds"

  def incrementStatus(self):
    self.status += 1
    new_dot_count = int(self.status_size * ((self.status*1.0) / self.pcount))
    if new_dot_count > self.dot_count:
      self.dot_count = new_dot_count
      sys.stdout.write(".")

"""Gets costs for all seeds of a metarun. Simply generates each permutation one after another, simulates and calculates the cost."""
def getCostsForAllSeeds1(metarun, cost_func, gdata, gstate, do_status_bar=True, print_stats=False):

  #don't forget this so options get reset
  metarun.resetOptionSet()
  pcount = metarun.permutationCount()
  print "permutation count is", pcount

  #for status bar
  #do_status_bar=False
  status_size = 40
  if do_status_bar:
    status_bar = StatusBar()
    status_bar.start(status_size, pcount+1)

  #print some stats for each permutation
  #print_stats = True

  cost_func_results = []
  current_status = 0
  for seed in range(pcount):
    run = metarun.makeRunSegments(seed)
    option_cost = metarun.optionCosts()
    fight_list = getFightListFromSegments(run, gdata, gstate)
    cost = cost_func.costFunctionByFightList(run, fight_list)
    cost_func_results.append(cost+option_cost)
    if print_stats:
      print cost, option_cost, len(fight_list), countNoRunFights(fight_list, gdata),
    last_status = current_status
    if do_status_bar:
      status_bar.incrementStatus()
  if do_status_bar:
    status_bar.finish()

  return cost_func_results

def getFightListFromSegment(segment, gdata, gstate):
  """given some information, simulate one segment of a run.
  The segment must be in only one area.
  Returns a list of enemy group ids."""
  step_sequence = gstate.takeSteps(segment.steps)
  threshold = gdata.area_thresholds[segment.area_id]
  fight_list = []
  for i in step_sequence:
    if gdata.threshold_list[i] < threshold:
      btype_counter = gstate.getAndUpdateTypeCounter()
      btype = gdata.group_order[btype_counter]-1
      group_id = gdata.area_groups[segment.area_id][btype]
      fight_list.append(group_id)
  return fight_list

def getFightListFromSegments(run_data, gdata, gstate, doPowerCycle=True):
  """Given a sequence of segments, simulate the whole thing.
  Save/Power cycle is done on an empty list in the list"""
  if doPowerCycle:
    gstate.powerCycle()
  fight_list = []
  for segment in run_data.run:
    if segment.isPowerCycle:
      gstate.powerCycle()
    else:
      fight_list += getFightListFromSegment(segment, gdata, gstate)
  return fight_list

def getResultsFromSegment(segment, gdata, gstate):
  step_sequence = gstate.takeSteps(segment.steps)
  threshold = gdata.area_thresholds[segment.area_id]
  results = ResultSegments()
  step_count = 0
  for i in step_sequence:
    step_count += 1
    if gdata.threshold_list[i] < threshold:
      btype_counter = gstate.getAndUpdateTypeCounter()
      btype = gdata.group_order[btype_counter]-1
      group_id = gdata.area_groups[segment.area_id][btype]
      results.addSegment(ResultSegment(segment.area_id, step_count, group_id))
      step_count = 0

  #document extra steps
  results.addSegment(ResultSegment(segment.area_id, step_count, -1))
  return results

def getResultsFromSegments(run_data, gdata, gstate, doPowerCycle=True):
  if doPowerCycle:
    gstate.powerCycle()
  results = ResultSegments()
  for segment in run_data.run:
    if segment.isPowerCycle:
      gstate.powerCycle()
      results.addNote("power cycle")
    elif segment.steps <= 0:
      #check to see if it's just a note
      results.addNote(segment.note)
    else:
      results.addSegments(getResultsFromSegment(segment, gdata, gstate))
  return results

def fightListToString(results, gdata):
  """Translates results from id list to human-readable report"""
  #result is a list of enemy group ids
  result_string = ""
  for group in results:
    group_name = gdata.enemy_groups[group]
    result_string += group_name
    result_string += "   "
    if group_name in gdata.noRunList:
      result_string += "***can't run***"
    elif group_name in gdata.shadowList:
      result_string += "***shadows!!***"
    else:
      result_string += "               "
    result_string += "   "
    enemies_in_group = gdata.group_info[group_name]
    result_string += ", ".join(enemies_in_group)
    result_string += "\n"
  return result_string

def fightListToNames(results, gdata):
  """Translates results from id list to list of names"""
  #result is a list of enemy group ids
  result_names = []
  for group in results:
    group_name = gdata.enemy_groups[group]
    result_names.append(group_name)
  return result_names

def main():
  gdata = GameData()
  gdata.loadData()
  gstate = GameState()

  #first, load up the run information
  run = RunSegments()
  run.loadFromFile("wmstepList.txt")
  #translate from strings naming areas to indexes
  run.translate(gdata)
  #run.printRun()

  #get fight_list
  gstate.powerCycle()
  fight_list = getFightListFromSegments(run, gdata, gstate)
  #get full results
  gstate.powerCycle()
  results = getResultsFromSegments(run, gdata, gstate)

  print len(fight_list), "encounters in fight list and",results.totalEncounters(), "in results"

  print fightListToNames(fight_list, gdata)

  results.compareToFightList(fight_list)

  return

  #print out some stats
  print "this run is", results.totalSteps(), "steps long and has", results.totalEncounters(), "encounters"
  print "there are", results.noRunFightCount(gdata), "no-run fights and", results.shadowFightCount(gdata), "shadow fights"
  result_string = results.getReport(gdata)

  print result_string
  report_file = open("ffpf_results.txt", "w")
  report_file.write(result_string)
  report_file.close()

  return
 
def test_tree_sim():
  #load game data
  gdata = GameData()
  gdata.loadData()
  #init game state
  gstate = GameState()
  gstate.powerCycle()

  #load up cost function
  cost_func = CostFunction(gdata)

  #first, load up the run information
  metarun = MetaRunSegments()
  metarun.loadFromFile("ultimateRunPart1.txt", gdata)
  #metarun.loadFromFile("ultimateRunFull.txt", gdata)
  #metarun.loadFromFile("test2.txt", gdata)
  #metarun.printRun()
  print "metarun has",len(metarun.option_flags),"options"

  #old way
  print "old method"
  print "-----------"
  cost_func_results = getCostsForAllSeeds1(metarun, cost_func, gdata, gstate, True, True)
  old_results = cost_func_results

  min_cost = cost_func_results[0]
  min_cost_seed = 0
  metarun.resetOptionSet()
  pcount = metarun.permutationCount()
  print "pcount is",pcount
  for seed in range(pcount):
    if cost_func_results[seed] <= min_cost:
      min_cost = cost_func_results[seed]
      min_cost_seed = seed

  print "best seed is", min_cost_seed, "with a cost of", min_cost
  print cost_func_results

  #new way
  print "new method"
  print "-----------"
  tree_sim = TreeSimNode()
  cost_func_results = tree_sim.getCostsForAllSeeds(metarun, cost_func, gdata, gstate)

  print cost_func_results
  #requires fight count debug on
  if False:
    fight_counts = []
    for i in range(len(cost_func_results)/2):
      cost_func_results.append(cost_func_results.pop(0))
      fight_counts.append(cost_func_results.pop(0))

  min_cost = cost_func_results[0]
  min_cost_seed = 0
  pcount = metarun.permutationCount()
  for seed in range(pcount):
    if cost_func_results[seed] <= min_cost:
      min_cost = cost_func_results[seed]
      min_cost_seed = seed

  print "best seed is", min_cost_seed, "with a cost of", min_cost

  diff_list = []
  #print "old", "new"
  for i in range(len(cost_func_results)):
    #print old_results[i], cost_func_results[i]
    if old_results[i] != cost_func_results[i]:
      diff_list.append([i, old_results[i], cost_func_results[i]])
  if len(diff_list) == 0:
    print "identical results from both methods"
  else:
    print "results differ for",len(diff_list),"seeds:"
    for i in diff_list:
      print i

  #sorted_old = old_results[:]
  #sorted_old.sort()
  #sorted_new = cost_func_results[:]
  #sorted_new.sort()
  #diff_list = 0
  #for i in range(len(sorted_old)):
    #if sorted_old[i] != sorted_new[i]:
      #diff_list += 1
  #print "after sorting",
  #if diff_list == 0:
    #print "identical results from both methods"
  #else:
    #print "results differ for",len(diff_list),"seeds"

  #get full results with notes
  metarun.resetOptionSet()
  best_run = metarun.makeRunSegments(min_cost_seed, True)
  option_cost = metarun.optionCosts()
  results = getResultsFromSegments(best_run, gdata, gstate)

  #print out some stats
  print "the best run is", results.totalSteps(), "steps long and has", results.totalEncounters(), "encounters"
  print "there are", results.noRunFightCount(gdata), "no-run fights and", results.shadowFightCount(gdata), "shadow fights"

  #calculate cost
  cost = cost_func.costFunctionFromResults(results)
  print "cost function result: ", cost
  print "option cost: ", option_cost
  print "total: ", cost+option_cost

  result_string = results.getReport(gdata)
  #print result_string
  report_file = open("ffpf_results.txt", "w")
  report_file.write(result_string)
  report_file.close()

  return
  

if __name__ == "__main__":
  #main()
  test_tree_sim()


